package com.gy.algorithm.carl.linklistexa;

import java.util.List;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl
 * @Author: gy
 * @Date: 2024/10/22 11:30
 * @Description:
 */
public class GetIntersectionNode02_07 {

    public static ListNode getListNode(int[] nums){
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode cur = dummy;
        for (int i = 0; i < nums.length; i++) {
            cur.next = new ListNode(nums[i]);
            cur = cur.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = getListNode(new int[]{4,1,8,4,5});
        ListNode listNode2 = getListNode(new int[]{5,0,1,8,4,5});

        ListNode listNode = getIntersectionNode(listNode1,listNode2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    // end 长短链表加起来 相交节点前的长度是一样长的。
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA != curB){
            if(curA == null) curA = headB;
            else curA = curA.next;

            if(curB == null) curB = headA;
            else curB = curB.next;
        }

        return curA;
    }


    // write
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;

        // 计算两个链表长度
        int lenA = 0;
        int lenB = 0;

        ListNode curA = headA;
        ListNode curB = headB;

        while(curA != null){
            curA = curA.next;
            lenA++;
        }

        while(curB != null){
            curB = curB.next;
            lenB++;
        }

        int lenSub = lenA > lenB ? lenA - lenB : lenB - lenA;
        boolean isA = lenA > lenB ? true : false;

        // 处理长链表数据
        curA = headA;
        curB = headB;

        for (int i = 0; i < lenSub; i++) {
            if(isA){
                curA = curA.next;
            }else{
                curB = curB.next;
            }
        }

        // 遍历两个链表取交点
        while (null != curA && null != curB){
            // 核心在于是对象相等
            if(curA == curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
